package 每日一题;

import 链表.ListNode;

public class No92反转链表II {

    /**
     * 给你单链表的头指针 head 和两个整数 left 和 right ，
     * 其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
     *  
     * 示例 1：
     * 输入：head = [1,2,3,4,5], left = 2, right = 4
     * 输出：[1,4,3,2,5]
     * 示例 2：
     * 输入：head = [5], left = 1, right = 1
     * 输出：[5]
     *  
     * 提示：
     * 链表中节点数目为 n
     * 1 <= n <= 500
     * -500 <= Node.val <= 500
     * 1 <= left <= right <= n
     * 进阶： 你可以使用一趟扫描完成反转吗？
     */

    public ListNode reverseBetween(ListNode head, int left, int right) {

        if(head==null){
            return null;
        }

        if(left==right){
            return head;
        }

        int length=1;
        ListNode cur=head;
        ListNode lastNode=null;
        ListNode endNode=null;

        while (cur!=null){
            if(length==left-1){
                lastNode=cur;
            }
            if(length==right){
                endNode=cur;
            }
            cur=cur.next;
            length++;
        }

        if(lastNode==null){
            //从0开始的
            ListNode next=endNode.next;
            endNode.next=null;
            ListNode listNode = this.reverseListNode(head);
            head.next=next;
            return listNode;
        }else {
            ListNode node1 = lastNode.next;
            ListNode nextNode = endNode.next;
            endNode.next = null;
            ListNode listNode = this.reverseListNode(node1);
            lastNode.next = listNode;
            node1.next = nextNode;
        }
        // 1->2->3->4->5
        // 1->4->3->2->5
        return head;
    }

    private ListNode reverseListNode(ListNode node){
        ListNode cur=node;
        ListNode last=null;
        ListNode next=null;

        // 1->2->3
        while (cur!=null){
            next=cur.next;
            cur.next=last;
            last=cur;
            cur=next;
        }

        return last;
    }

    public static void main(String[] args) {
        No92反转链表II n=new No92反转链表II();
        ListNode listNode = ListNode.createListNode(new int[]{1, 2, 3, 4, 5, 6, 7});
        ListNode result = n.reverseBetween(listNode, 1, 7);
        ListNode.printListNode(result);
    }

}
